﻿#include <stdio.h>
#include <stdbool.h>

#define N 5  // 进程数量
#define M 3  // 资源数量

// 最大需求矩阵
int max_need[N][M] = 
{
    {7, 5, 3},
    {3, 2, 2},
    {9, 0, 2},
    {2, 2, 2},
    {4, 3, 3}
};

// 分配矩阵
int allocation[N][M] = 
{
    {0, 1, 0},
    {2, 0, 0},
    {3, 0, 2},
    {2, 1, 1},
    {0, 0, 2}
};

// 可用资源向量
int available[M] = { 3, 3, 2 };

// 需求矩阵
int need[N][M];

bool is_safe() 
{
    int work[M];
    bool finish[N];
    int safe_sequence[N];
    int index = 0;

    // 初始化 work 为 available 的副本
    for (int i = 0; i < M; i++) 
    {
        work[i] = available[i];
    }
    // 初始化 finish 数组
    for (int i = 0; i < N; i++) 
    {
        finish[i] = false;
    }

    while (1) 
    {
        bool found = false;
        for (int i = 0; i < N; i++) 
        {
            if (!finish[i]) 
            {
                bool can_allocate = true;
                for (int j = 0; j < M; j++) 
                {
                    if (need[i][j] > work[j]) 
                    {
                        can_allocate = false;
                        break;
                    }
                }
                if (can_allocate) 
                {
                    for (int j = 0; j < M; j++) 
                    {
                        work[j] += allocation[i][j];
                    }
                    finish[i] = true;
                    
                    //这个安全队列实际上起到的作用是指导操作系统先执行哪一个进程的作用  
                    //因为现在存在的资源不一定能够支持先检测的进程先执行，
                    //所以操作系统会先将能够执行的进程先执行，然后回收这个进程申请的资源
                    //然后再重新检测进程，这样这个进程就有可能可以执行。
                    //安全队列就是一个能够直到操作系统执行进程，保证进程执行后系统资源最大化的一个队列。
                    safe_sequence[index++] = i;
                    found = true;
                }
            }
        }
        if (!found) 
        {
            break;
        }
    }

    // 检查是否所有进程都完成
    for (int i = 0; i < N; i++) 
    {
        if (!finish[i]) 
        {
            return false;
        }
    }
    return true;
}

bool request_resources(int process_id, int request_vector[M]) 
{
    for (int j = 0; j < M; j++) 
    {
        if (request_vector[j] > need[process_id][j]) 
        {
            printf("请求超过最大需求，拒绝请求\n");
            return false;
        }
        if (request_vector[j] > available[j]) 
        {
            printf("请求超过可用资源，进程等待\n");
            return false;
        }
    }

    // 尝试分配资源
    for (int j = 0; j < M; j++) 
    {
        available[j] -= request_vector[j];
        allocation[process_id][j] += request_vector[j];
        need[process_id][j] -= request_vector[j];
    }

    // 检查安全性
    if (is_safe()) 
    {
        printf("资源分配成功\n");
        return true;
    }
    else 
    {
        printf("分配后系统不安全，撤销分配\n");
        for (int j = 0; j < M; j++) 
        {
            available[j] += request_vector[j];
            allocation[process_id][j] -= request_vector[j];
            need[process_id][j] += request_vector[j];
        }
        return false;
    }
}

int main() 
{
    // 计算需求矩阵
    for (int i = 0; i < N; i++) 
    {
        for (int j = 0; j < M; j++) 
        {
            need[i][j] = max_need[i][j] - allocation[i][j];
        }
    }

    // 示例请求
    int request_vector[M] = { 1, 0, 2 };
    int process_id = 1;
    request_resources(process_id, request_vector);

    return 0;
}